Skip to main content

617. Merge Two Binary Trees

문제​

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

예제 입출력​

img

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
참고

You can read the full description here.

풀이 1​

접근법​

  1. 전위순회하면서 트리를 병합합니다. 매개변수로 두 루트와 결과 노드를 가져갑니다.

구현 코드​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        result: Optional[TreeNode] = None

        def preorder(root1: Optional[TreeNode], root2: Optional[TreeNode], result: Optional[TreeNode]):
            result.val += root1.val if root1 else 0
            result.val += root2.val if root2 else 0

            if root1 and root1.left or root2 and root2.left:
                result.left = TreeNode()
                preorder(root1.left if root1 else None, root2.left if root2 else None, result.left)

            if root1 and root1.right or root2 and root2.right:
                result.right = TreeNode()
                preorder(root1.right if root1 else None, root2.right if root2 else None, result.right)

            return

        if root1 or root2:
            result = TreeNode()
            preorder(root1, root2, result)

        return result

복잡도 분석​

  • R1,R2R1, R2: root1, root2의 노드 수
  • 시간복잡도: O(R1+R2)O(R1 + R2)

책에 있는 풀이​

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2​

접근법​

  1. 풀이 1과 유사합니다.

구현 코드​

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 and t2:
            node = TreeNode(t1.val + t2.val)
            node.left = self.mergeTrees(t1.left, t2.left)
            node.right = self.mergeTrees(t1.right, t2.right)

            return node
        else:
            return t1 or t2

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)